﻿#define _CRT_SECURE_NO_WARNINGS 1

//https://leetcode.cn/problems/minimum-window-substring/

class Solution
{
public:
    string minWindow(string s, string t)
    {
        int hash1[128] = { 0 }; // 统计字符串 t 中每⼀个字符的频次
        int kinds = 0; // 统计有效字符有多少种
        for (auto ch : t)
            if (hash1[ch]++ == 0) kinds++;
        int hash2[128] = { 0 }; // 统计窗⼝内每个字符的频次
        int minlen = INT_MAX, begin = -1;
        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            char in = s[right];
            if (++hash2[in] == hash1[in]) count++; // 进窗⼝ + 维护 count
            while (count == kinds) // 判断条件
            {
                if (right - left + 1 < minlen) // 更新结果
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if (hash2[out]-- == hash1[out]) count--; // 出窗⼝ + 维护 count
            }
        }
        if (begin == -1) return "";
        else return s.substr(begin, minlen);
    }
};